//
// Created by andrew on 2022/5/10.
//

#include <vector>

using namespace std;

// https://leetcode.cn/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
/*
 若暴力枚举，水槽两板围成面积 S(i, j)S(i,j) 的状态总数为 C(n, 2)C(n,2) 。
假设状态 S(i, j)S(i,j) 下 h[i] < h[j]h[i]<h[j] ，在向内移动短板至 S(i + 1, j)S(i+1,j) ，则相当于消去了 {S(i, j - 1), S(i, j - 2), ... ,
 S(i, i + 1)}S(i,j−1),S(i,j−2),...,S(i,i+1) 状态集合。而所有消去状态的面积一定都小于当前面积（即 < S(i, j)<S(i,j)），因为这些状态：
短板高度：相比 S(i, j)S(i,j) 相同或更短（即 \leq h[i]≤h[i] ）；
底边宽度：相比 S(i, j)S(i,j) 更短；
因此，每轮向内移动短板，所有消去的状态都 不会导致面积最大值丢失 ，证毕。

 * */



class Solution {
public:
    static int maxArea(vector<int>& height) {
        int l = 0, r = static_cast<int>(height.size()) - 1, area = 0;

        while (l < r) {
            if (height[l] < height[r]) {
                area = std::max(area, (r - l) * height[l]);
                l ++;
            } else {
                area = std::max(area, (r - l) * height[r]);
                r --;
            }
        }

        return area;
    }

//    static int maxArea(vector<int>& height) {
//        auto size = height.size();
//        // 两种特殊情况需要单独处理
//        if (size <= 1) {
//            return 0;
//        }
//
//        if (size == 2) {
//            return std::min(height[0], height[1]);
//        }
//
//        int area = 0;
//        for (auto i = 0; i < size; ++i) {
//            for (auto j = i + 1; j < size; ++j) {
//                area = std::max(area, std::min(height[i], height[j]) * (j - i));
//            }
//        }
//
//        return area;
//    }
};




#include <gtest/gtest.h>


TEST(ListTest1, ListTest) {

    vector<int> areaData = {1,8,6,2,5,4,8,3,7};
    ASSERT_EQ(49 , Solution::maxArea(areaData));

}


